//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
//
// 
// 
// 
// 
// 
//
// 示例 1： 
// 
// 
//输入：head = [1,2,3,4,5]
//输出：[5,4,3,2,1]
// 
//
// 示例 2： 
// 
// 
//输入：head = [1,2]
//输出：[2,1]
// 
//
// 示例 3： 
//
// 
//输入：head = []
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目范围是 [0, 5000] 
// -5000 <= Node.val <= 5000 
// 
//
// 
//
// 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？ 
//
// Related Topics 递归 链表 👍 3860 👎 0


//leetcode submit region begin(Prohibit modification and deletion)


import java.util.List;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 方法1 - 迭代
//        ListNode prev = null;
//        ListNode curr = head;
//        while (curr != null) {
//            ListNode next = curr.next;
//            curr.next = prev;
//            prev = curr;
//            curr = next;
//        }
//        return prev;
        // 方法2
//        ListNode n1 = null;
//        ListNode n2 = head;
//        while(n2 != null){
//            n1 = new ListNode(n2.val, n1);
//            n2 = n2.next;
//        }
//        return n1;
        //详细
        //head = 1 -> 2 -> 3 -> 4 -> 5 -> null
        //pointer 代表旧链接的指针，首次指向1，迭代过程中每次都指向当前节点，最后指向空。
        //newList = null <- 1 <- 2 <- 3 <- 4 <- 5
        ListNode newListHead = null;//新链表首次初始化为空
        ListNode pointer = head; //旧链表指针
        while(pointer != null){
            newListHead = new ListNode(pointer.val, newListHead);//构建新链表头节点
            pointer = pointer.next;//旧链表指针移动
        }
        return newListHead;
//        // 方法3(不能用)
//        ListNode list1 = new MyList(head);
//        ListNode list2 = new MyList(null);
//        while(true){
//            ListNode first = list1.removeFirst();
//            if(first == null){
//                break;
//            }
//            list2.addFirst(first);
//        }
//        return list2.head;
    }


}

////方法3 构建链表类
// class MyList{
//    ListNode head;
//    public MyList(ListNode head){
//        this.head = head;
//    }
//    public void addFirst(ListNode first){
//        first.next = head;
//        head = first;
//    }
//    public ListNode removeFirst(){
//        ListNode first = head;
//        if(first != null){
//            head = first.next;
//        }
//        return first;
//    }
//}
//leetcode submit region end(Prohibit modification and deletion)
